package com.lw.leetcode.arr.b;

import java.util.ArrayList;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * 1447. 最简分数
 *
 * @author liw
 * @version 1.0
 * @date 2021/11/9 13:17
 */
public class SimplifiedFractions {


    public List<String> simplifiedFractions(int n) {
        List<String> res = new ArrayList<>();
        for (int b = 2; b <= n; b++) {
            for (int a = 1; a < b; a++) {
                if (find(a, b) == 1) {
                    res.add(a + "/" + b);
                }
            }
        }
        return res;
    }

    private int find(int a, int b) {
        if (b == 0) {
            return a;
        }
        return find(b, a % b);
    }

}
